#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;


void getMax(stack<int> &myStack, vector<int> &height, int i, int &maxArea)
{
    int top = myStack.top();
    int high = height[top];
    myStack.pop();
    int right = i, left = myStack.empty()? -1 : myStack.top();
    int area = high * (right - left-1);
    if (maxArea < area)
         maxArea = area;
}

class Solution {
    public:
        int largestRectangleArea(vector<int> &height) {
            if (height.size() == 0) return 0;
            stack<int> myStack;
            int maxArea =-1 ;
            for (int i = 0; i < height.size(); i++) {
                if (myStack.empty() || height[myStack.top()] <= height[i]) {
                    myStack.push(i);
    				continue;
				}
                while(!myStack.empty() && height[myStack.top()] > height[i])
                    getMax(myStack, height, i, maxArea);
                myStack.push(i);
            }
            while(!myStack.empty())
                    getMax(myStack, height, height.size(), maxArea);

            return maxArea;
        }
};
//add better code
int cal(stack<int> &stk, const vector<int> &height, int right)
{
    int h = height[stk.top()];
    stk.pop();
    int left = stk.empty() ? -1 : stk.top();
    return (right - left - 1) * h;
}


    int largestRectangleArea(vector<int> &height) {
        stack<int> stk; 

        int maxArea = 0;
        for (int i = 0; i < height.size(); i++) {
            if (stk.empty() || height[i] >= height[stk.top()]) stk.push(i);
            while(!stk.empty() && height[i] < height[stk.top()]) {
                maxArea = max(maxArea, cal(stk, height, i));
            }   
            stk.push(i);
        }   
        while(!stk.empty()) 
            maxArea = max(maxArea, cal(stk, height, height.size()));
        return maxArea; 
    }



int main(int argc, char **argv)
{
    Solution mySolution;

    cout << "-----------------Test 1--------------------" << endl;
    int input[] = {2,1,5,6,2,3};
    vector<int> num;
    for (int i = 0; i < sizeof(input)/sizeof(int); i++)
        num.push_back(input[i]);
    int area = mySolution.largestRectangleArea(num);
    cout << "Area is " << area << endl;

    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
